COS
Cellular Operating Systems COS (Cooperating Operating Systems or Co-Operating Systems for short) are operating systems where the functionality of the Operating System is spread across many small cooperating OS processors. COS are a first attempt at building a platform for GREAT Computing. This page is an overview of Cooperating Operating Systems. It summarises the following sections of this wiki: * Problem Definition * Background * Abstract Operating Systems * Eager Queue Protocols Context Application Area - General Purpose Computing The design presented here is targetted at general purpose computing. We are looking for an architecture that provides reasonable performance across many problem domains. The architecture is not aimed specifically at HTC (High Throughput Computing) and in particular is not aimed at computing where the architecture can be optimised before computing starts. Process networks in general purpose computing tend to lack regular structure. It is the intention that a COS can easily configure process networks with irregular structures. Assumptions To simplify the initial development some assumptions have been made. The main assumption that is being made is that there is a large number of processors. This largely removes the need for a scheduler. The assumption is not totally unfounded. In the late 1980s Ivor Catt proposed a Kernel machine with 1,000,000 cores. * Large number of processors ** Catt Kernel http://www.patentstorm.us/patents/5055774.html ** Intel's Single Chip Cloud Computer Design Objectives Reliability and energy efficiency are becoming dominant constraints in the design of computing systems. These are the primary design objectives for a COS. Traditionally the most expensive part of a computer has been the central processing unit. The original computers were expensive from a manufacturing perspective. Modern microprocessors are expensive from an energy perspective. Linking Text In the design of a Co-Operating System we want to aim at satisfying Tanebaum's 3 principles (Tanenbaum, 2001, pp 859-861): * Principle 1: Simplicity * Principle 2: Completeness * Principle 3: Efficiency Development of a COS If we start by looking at the objectives for a platform for GREAT computing we have the following list: * Guaranteed * Reliable * Efficient * Affordable * Testable Abstract Operating Systems Abstract Operating Systems are a way of investigating the different aspects of operating systems. The main concern here is with process management. Other areas include spatial multiplexing, energy efficiency, fault tolerance and program correctness. Guaranteed It is only possible to guarantee a system if there is confidence in it operating correctly. The work on this page mainly relies on guaranteeing that the system meets it specification with (physically) reliable components. A COS can also handle fault tolerance. If the system is fault tolerant a guarantee can have a wider scope. Reliable If we return to the hypothesis for this work, it states: We want an architecture where we can prove our systems correct. It is generally accepted that to enable proofs to be feasible a system must be component based. When working bottom-up we want the PQ cells to be the basic component that provides a foundation. In Can We Make Operating Systems Reliable and Secure? (Tanenbaum et al., 2006) the authors consider 4 attempts at improving the reliability and security of operating systems: # Armored Operating Systems # Paravitual machines # Microkernels # Singularity Approaches 1 and 2 are intended to improve the reliability of existing (legacy) systems. 3 and 4 replace legacy operating systems with more reliable and secure ones. The multiserver approach runs each driver and operating system component in a separate user process nd allows them to communicate using the microkernel's IPC mechanism. Finally, Singularity, the most radical approach, uses a type-safe language, a single address space, and formal contracts to carefully limit what each module can do. A COS makes the basic component a process and isolates the process in hardware. Some of the ideas here come form the Singularity project (Hunt, Larus, 2007). In singularity processes run as software isolated processes. In a COS processes run as hardware isolated processes. Much of the work in singularity seems to reflect work based on the transputer. The main difference would appear to be that singularity is a more general purpose OS. Guarantees and Reliability - Need Reworking It is not easy to guarantee systems which are not reliable. Therefore the first objective for a COS is reliability. If we can build reliable systems we can guarantee them and meet the GR objectives. Refactoring the Microkernel The following diagram is from (Tanenbaum, 2001): Good system design consists of separate concerns that can be combined independently. (Tanenbaum, 2001, pp 871) In the design of a Co-Operating System we want to try and treat IPC, Process Management and Scheduling as orthogonal concepts. We start by separating process management and IPC using an IPC network. At the same time we note that process management can be broadened to resource management. Later we will broaden process management to include management of the IPC network. We have stated earlier that a major working assumption initially is that there is a large number of processors, We therefore run each server on its own processor and at the same time split the process management onto separate processors. In the diagram above it is not shown how the process managers communicate. The process managers are going to communicate over a dedicated broadcast network. At this point we also rename the process managers as QCells. The QCells are much smaller than the main processors. For the moment we also do not worry too much about the IPC network. Below we will show how the network can be managed in a similar way to the processors and also how processes working together can be kept in local proximity with each other. Basic PQ-Cells A PQ-Cell is a pair consisting of the Processor, P and the OS cell Q. In a basic PQ-Cell the Q-Cell is responsible for the management of processes running on the processors. Processors (P-Cells) communicate across an IPC (Inter Processor Network) network, this is mainly point to point. The Q-Cells communicate across an IQC (Inter Q-Cell Communication) network, this a broadcast network dedicated solely to the Q-Cells. Each PQ-Cell pair has a private communication channel. Given that we are assuming: * A large pool of processors * One process per processor Process management becomes a matter of: * Finding an available processor when there is a fork * Making a processor available when its process terminates. To do this the Q-Cells manage a queue of available processors. Each Q-Cell has a copy of the queue. When a process wants to fork: * The process running on P_1 makes a request to its QCell, Q_1 * Q_1 broadcasts a REQUEST * Q_2 managing the processor at the front of the queue, P_2 , broadcasts an ACCEPT * Q_1 notifies P_1 of the address of P_2 , Q_2 readies P_2 : \; P_4, \; P^*_1, \; P_5, \; P_3 : \; P_4, P^*_1, \; P_5, \; P_3 : \; P^*_2, \; P_4, P^*_1, \; P_5 QCells * Explain Eager Queues Explanation of Eager Queue Protocols The Eager Queue Protocols page contains a detail description of Eager Queues. Eager Queue Protocols were developed as a way of monitoring the state of distributed processors. What was wanted was an idea of how "live" the processors were. The first approach was to have each processor transmit a heartbeat and a record was kept of the heartbeats. The initial idea was to keep the record centrally, then it appeared better to have each processor keep its own copy of the heartbeat history. The heartbeat history or last known transmission vector would be an array of processor Ids and when the processor last transmitted, The last known transmission vector could be simplified if the heartbeats across the network were regular. The least recent processor to transmit would be the next expected processor to transmit. If this is the case only a queue of processor Ids is required with the most recent transmitter at the front and the least recent transmitter at the back. When a processor transmits it moves its processor Id to the front of the queue (hence the name Eager Queue at the processor at the back pushes to the front). The following diagram is a state transition diagram for a QCell. The states in the diagram are: * A - Accepting * B - Busy * D - Declining * E - Exiting * H - Holding * I - Idling * J - Joining * L - Listening * N - Not Accepting * Q - Queuing * R - Requesting * T - Transmitting * W - Waiting * Explanation of REQUEST -> ACCEPT * Image of REQUEST -> ACCEPT Some Thoughts on Performance How well will COS perform? To start with if we consider the simple protocol defined above we can put some timings in. Assume that a broadcast message takes 0.5 \mu Sec to broadcast, i.e. we have a top message rate of 2MHz . Once a REQUEST message is broadcast the channel is open for one ACCEPT message from the first free processor in the eager queue. If the processor is not exiting it accepts and broadcasts its ACCEPT message immediately. The REQUEST-ACCEPT pair has taken 1 \mu Sec . 1 \mu Sec is the time to fork a process. 1 \mu Sec is the best we can expect from the protocol defined above with a 2MHz peak message rate. However once we get a system like this up and running there is nothing to stop us making multiple requests for processors at once. Also if local queue cells can talk to each other the ACCEPT messages don't have to come in one at a time. It's quite conceivable that we could fork 100 processes in 10 \mu Sec . What allows things to happen qucikly is that the system is self aware. Efficient Up to this point we have been looking at a COS from the perspective of reliability. Of equal importance to reliability is efficiency. We look at the management of energy efficiency from two perspectives. * Control of the P Cell energy use by their Q cells. * Control of the QCell network energy use by the QCell network. Control of P-Cell Energy Use Control of the processor (P-Cell) is straight forward. A control line is added so the Q-Cell can turn the P-Cell on and off. The Q-Cell acts as a proxy for the P-Cell. When the P-Cell is idle the Q-Cell turns it off. When a Q-Cell accepts a request, it sends an !!ACCEPT broadcast and turns the P-Cell on. : Queuing_i(q) \; \rightarrow \; ??REQUEST(P_i + q') \; \rightarrow \; (P_i.On() \; | \; !!ACCEPT(P^*_j + q')) \; \rightarrow \; Busy_i(P^*_j + q') Control of the QCell Network Energy Use So far we have considered how a QCell can control the state of its P co-processor. This still leaves a problem. If we have a network of 1,000,000 PQ-Cells then when the system is in an idling state there will still be 1,000,000 QCells running. However as each QCell knows the state of the system QCells can power one another on and off. This has similarities to the Game of Life Conway's_Game_of_Life. The main difference being that QCell that are running have a much more state information. We add control lines in as show in the following diagram. This PQ-Cell is then replicated. Control of Number of QCells with Fixed Reference Now that QCells can control the state of their neighbours we need to consider how this is managed. A simple scenario would be to require a fixed number of idling cells, N-R is the required number. The current number of idling cells (N-I) is then fed back and the difference (N-R - N-I) is used to control the QCells. This feedback is limited by the fact that N-R is a constant or at least is provided by an external source. Control of Number of QCells with Dynamic Reference It is likely that the number of idling processors will want to be higher when there are more busy processors. N-R can be made dynamic by basing it on the number of busy processors N-B. Control of Number of QCells with Adaptive Reference A more general approach to controlling the network is to allow feedback to and from the processors. In this way policy can be handed over to the processor network when needed. Once we have this sort of feedback the network of processors can be controlled to the extent that before high work loads the reserve pool can be increased. During low workloads the reserve pool can be run down. Affordable Throughout the design of a COS one of the design objectives has been Simplicity. The architecture presented is based around 1 type of cell. This greatly simplifies the detailed implementation. This should reduce manufacturing costs. From a programmability point of view current software can be gradually migrated to take adavantage of the COS architecture. It should be possible to expose a POSIX API to programs running on a COS. Testable Notation Processors will be denoted by P_{Id} where a capital P indicates a processor and Id is the identity (address) of the processor. A processor that is busy (i.e. is running a process) will have a superscript asterisk, P^* . Queues Queues will use standard list notation (cf. python): * [ \; ] is the empty queue. * \; P_2, \; P_3, \; P_4 is a queue with 4 members, P_1 is at the front of the queue, P_4 is at the back. ''Temporary Notes'' * Transputer * Singularity * Microkernel * Law of Demeter * Catt Spiral/Kernel * CSK * Per Brinch Hansen The main service of an operating system is process management. Process management consists of: * Creating Processes * Scheduling Processes * Destroying Processes Key Points # COS is aimed at general purpose computing. # Separates the Operating System from the Applications # Decentralised # Aims to run with Just Enough Power # Fast Boot as each process boots in parallel # Processes run on isolated Processors (cores) # Simple Cell Architecture - PQ Cells Relation to Microkernels A COS is very similar to a Microkernel in that it tries to implement the minimal functionality. wikipedia:Microkernel#Essential_components_and_minimality Microkernel - Essential Components and Minimality It states as a microkernel must allow building arbitrary operating system services on top, it must provide some core functionality. At the least this includes: # some mechanisms for dealing with address spaces — this is required for managing memory protection; # some execution abstraction to manage CPU allocation — typically threads or scheduler activations; and # inter-process communication — required to invoke servers running in their own address spaces. This minimal design was pioneered by Brinch Hansen's Nucleus (Brinch Hansen, 1970) and the hypervisor of IBM's VM. A COS satisfies these as follows: # Processes run on separate processors, this provides the first part of memory protection. # The execution abstraction is parallel processors. # This is an open question at the moment. There are several possible approaches. Process Granularity A COS Architecture Difficulties in Implementing a COS See Also Operating System Research Category:Research